public class Solution306 {
    public boolean isAdditiveNumber(String num) {
        int n=num.length();
        for (int i=1;i<n;i++){
            for (int j=1;j<n-i;j++){
                String s1=num.substring(0,i);
                String s2=num.substring(i,i+j);
                String rest=num.substring(i+j);
                if (rest.length()==0 || s1.length()>1 && s1.startsWith("0") || s2.length()>1 && s2.startsWith("0")){
                    continue;
                }
                while (true){
                    String temp=add(s1,s2);
                    if (rest.indexOf(temp)!=0){
                        break;
                    }
                    rest=rest.substring(temp.length());
                    if (rest.length()==0){
                        return true;
                    }
                    s1=s2;
                    s2=temp;
                }
            }
        }
        return false;
    }

    public String add(String s1,String s2){
        if (s2.length()>s1.length()){
            String temp=s1;
            s1=s2;
            s2=temp;
        }
        char[] chars1=s1.toCharArray();
        char[] chars2=s2.toCharArray();
        int[] ints1=new int[s1.length()];
        int[] ints2=new int[s1.length()];
        int[] ints3=new int[s1.length()+1];
        for (int i=s1.length()-1;i>=0;i--){
            ints1[i]=chars1[s1.length()-i-1]-'0';
        }
        for (int i=s2.length()-1;i>=0;i--){
            ints2[i]=chars2[s2.length()-i-1]-'0';
        }
        for (int i=s2.length();i<s1.length();i++){
            ints2[i]=0;
        }
        int carry=0;
        for (int i=0;i<s1.length();i++){
            ints3[i]=ints1[i]+ints2[i]+carry;
            carry=0;
            if (ints3[i]>=10){
                ints3[i]-=10;
                carry+=1;
            }
        }
        int flag=0;
        if (carry==1){
            ints3[s1.length()]=1;
            flag=1;
        }
        StringBuilder stringBuilder=new StringBuilder();
        int start=flag==0?s1.length()-1:s1.length();
        for (int i=start;i>=0;i--){
            stringBuilder=stringBuilder.append(ints3[i]);
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        System.out.println(new Solution306().isAdditiveNumber("199100199"));
    }
}
